翻訳と辞書 Words near each other ・ Plugs for the Program ・ Plugtest ・ Plugtown, Wisconsin ・ Pluguffan ・ Plugușorul ・ Pluherlin ・ Pluhův Žďár ・ Pluit ・ Pluk ・ Pluk de nacht ・ PLR ・ PLRA ・ PLRG1 ・ Plri ・ PLS ・ PLS (complexity) ・ PLS (file format) ・ PLS3 ・ PLSCR1 ・ PLSCR2 ・ PLSCR3 ・ PLSCR4 ・ PLSCR5 ・ PLSS ・ PLT ・ PLU ・ Plua ・ Pluak Daeng District ・ Pluchea ・ Pluchea baccharis Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク PLS (complexity) ： ウィキペディア英語版 PLS (complexity) In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. A PLS problem $L$ has a set $D\_L$ of instances which are encoded using strings over a finite alphabet $\backslash Sigma$. For each instance $x$ there exists a finite solution set $F\_L(x)$. Each solution $s\; \backslash in\; F\_L(x)$ has a non negative integer cost given by a function $c\_L(s,\; x)$ and a neighborhood $N(s,\; x)\; \backslash subseteq\; F\_L(x)$. Additionally, the existence of the following three polynomial time algorithms is required: * Algorithm $A\_L$ produces some solution $A\_L(x)\; \backslash in\; F\_L(x)$. * Algorithm $B\_L$ determines the value of $c\_L(s,\; x)$. * Algorithm $C\_L$ maps a solution $s\; \backslash in\; F\_L(x)$ to an element $s\text{'}\; \backslash in\; N(s,\; x)$ such that if such an element exists. Otherwise $C\_L$ reports that no such element exists. An instance $D\_L$ has the structure of an implicit graph, the vertices being the solutions with two solutions $s,\; s\text{'}\; \backslash in\; F\_L(x)$ connected by a directed arc iff $s\text{'}\; \backslash in\; N(s,\; x)$. The most interesting computational problem is the following: ''Given some instance $x$ of a PLS problem $L$, find a local optimum of $c\_L(s,\; x)$, i.e. a solution $s\; \backslash in\; F\_L(x)$ such that $c\_L(s\text{'},\; x)\; \backslash geq\; c\_L(s,\; x)$ for all $s\text{'}\; \backslash in\; N(s,\; x)$'' The problem can be solved using the following algorithm: # Use $A\_L$ to find an initial solution $s$ # Use algorithm $C\_L$ to find a better solution $s\text{'}\; \backslash in\; N(s,\; x)$. If such a solution exists, replace $s$ by $s\text{'}$, else return $s$ Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem $L$ can be solved exactly in polynomial time. Examples of PLS-complete problems include local-optimum relatives of the travelling salesman problem, maximum cut and satisfiability, as well as finding a pure Nash equilibrium in a congestion game. PLS is a subclass of TFNP, a complexity class closely related to NP that describes computational problems in which a solution is guaranteed to exist and can be recognized in polynomial time. For a problem in PLS, a solution is guaranteed to exist because the minimum-cost vertex of the entire graph is a valid solution, and the validity of a solution can be checked by computing its neighbors and comparing the costs of each one. == References == * . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PLS (complexity)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.